package algorithm.codingInterviewChinese2;

/**
 * 用一条语句判断一个整数是不是2的整数次方。
 * 一个整数如果是2的整数次方，那么它的二进制表示中有且仅有一位是1，而其它所有位都是0.
 * 根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0，
 * 整个运算的结果就是0
 *
 *  注：
 *  1，把一个整数减去1之后再和原来的整数进行位与运算，作用是把整数的二进制表示中最右边的1变成了0
 *  2，相邻的两个自然整数，大小相差1，最低位（最右）不同（0和1），必然有一个奇数，一个偶数。
 *  3，奇数：最右为1，偶数：最右为0
 *  4，一个字节byte(8 bit)               [ 1   1   1   1   1   1  1  1]
 *      每个bit上的1表示的数              128  64  32  16  8   4  2  1
 *      但128那个位置是符号位，不能参与计算，所以一个字节表示的最大值：64 + 32 + 16 + 8 + 4 + 2 + 1 = 127
 *  5，关于原码，反码，补码
 *  127 的二进制是   0 1 1 1 1 1 1 1，
 *  -128 的二进制是  1 0 0 0 0 0 0 0，只有补码，没有原码，没有反码
 *  （1）正数的原码，反码，补码都相等
 *  （2）负数
 *  反码：对该负数的原码除符号位外各位取反。
 *  补码：反码，加1。
 *  [+0]原码=0000 0000， [-0]原码=1000 0000
 *  [+0]反码=0000 0000， [-0]反码=1111 1111
 *  [+0]补码=0000 0000， [-0]补码=0000 0000
 *  [-0]反码1111 1111再+1后因为符号位发生了进位，得到[-0]补码1 0000 0000。
 *  9位二进制的[-0]补码1 0000 0000已经超出了8位二进制的位数限制，那只能保留最低的8位二进制，即最高位1要被舍弃，
 *  因此最后[-0]补码还是0000 0000。
 *
 *  验证第一条：
 *  例如  4的二进制表示  0 1 0 0  (二进制转换十进制：0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0)
 *       3 的二进制表示  0 0 1 1
 *   4和3作 与运算 得到  0 0 0 0 （4的二进制表示中那个1处在最右边，与运算之后变成0）
 *
 *       5 的二进制表示  0 1 0 1  （两个1）
 *       4 的二进制表示  0 1 0 0
 *   5和4作 与运算 得到  0 1 0 0 （只剩左边的1，最右边的1，与运算之后变成0）
 *
 *       6 的二进制表示  0 1 1 0  （两个1）
 *       5 的二进制表示  0 1 0 1
 *   6和5作 与运算 得到  0 1 0 0 （只剩左边的1，最右边的1，与运算之后变成0）
 *
 *      11 的二进制表示  1 0 1 1  （三个1）
 *      10 的二进制表示  1 0 1 0
 * 11和10作 与运算 得到  1 0 1 0 （只剩左边的1，最右边的1，与运算之后变成0）
 * 
 * netty源码中是这样判断的：
 * val & -val == val
 * 关键是：负数是正数的反码+1
 * 
 * +4的二进制表示  0000 0100，取反变成 1111 1011，再加1，得到1111 1100，这就是-4，即：
 * -4的二进制表示  1111 1100
 * & 结果是       0000 0100  这就是+4
 * 
 * +5的二进制表示  0000 0101，取反变成 1111 1010，再加1，得到1111 1011，这就是-5，即：
 * -5的二进制表示  1111 1011
 * & 结果是       0000 0001  这是+1
 */
public class Q015_JudgeNumber2Power {

    private static boolean numberIs2Power(int num) {
        boolean flag = false;
//        num &= num - 1;
        if ((num & (num - 1)) == 0) {
            flag = true;
        }
        return flag;
    }

    // netty源码
    // io.netty.util.concurrent.DefaultEventExecutorChooserFactory#newChooser
    private static boolean isPowerOfTwo(int val) {
        return (val & -val) == val;
    }

    public static void main(String[] args) {
        // 直接使用二进制表示
        int num = 0b0100;
        boolean flag = numberIs2Power(num);
        System.out.println(flag);

        num = 8;
        flag = isPowerOfTwo(num);
        System.out.println(flag);
    }
}
